home *** CD-ROM | disk | FTP | other *** search
/ Internet Surfer: Getting Started / Internet Surfer - Getting Started (Wayzata Technology)(7231)(1995).bin / pc / textfile / mac_faqs / graph / faq next >
Internet Message Format  |  1995-01-27  |  38KB
  1. Xref: bloom-picayune.mit.edu comp.graphics:34039 news.answers:4741
  2. Path: bloom-picayune.mit.edu!enterpoop.mit.edu!hri.com!spool.mu.edu!sdd.hp.com!elroy.jpl.nasa.gov!ufo!grieggs
  3. From: grieggs@jpl-devvax.jpl.nasa.gov (John T. Grieggs)
  4. Newsgroups: comp.graphics,news.answers
  5. Subject: (21Dec92) comp.graphics Frequently Asked Questions (FAQ)
  6. Message-ID: <1992Dec21.170230.6139@jpl-devvax.jpl.nasa.gov>
  7. Date: 21 Dec 92 17:02:30 GMT
  8. Expires: Mon, 4 Jan 1993 17:02:30 GMT
  9. Sender: grieggs@jpl-devvax.jpl.nasa.gov (John T. Grieggs)
  10. Reply-To: grieggs <grieggs@jpl-devvax.jpl.nasa.gov>
  11. Followup-To: poster
  12. Organization: Jet Propulsion Laboratory, Pasadena, CA
  13. Lines: 886
  14. Approved: news-answers-request@MIT.edu
  15.  
  16. Archive-name: graphics/faq
  17.  
  18. This message is automatically posted once a week or so in an effort to
  19. cut down on the repetitive junk in comp.graphics.  It was last changed
  20. on 21Dec92.  If you have answers to other frequently asked questions that
  21. you would like included in this posting, please send me mail.  If you
  22. don't want to see this posting every week, please add the subject line
  23. to your kill file.  Thank you.
  24. ---
  25. _john
  26.  
  27.     John Grieggs grieggs@jpl-devvax.jpl.nasa.gov JohnG@portal.com
  28. ---
  29. Last update: 21Dec92
  30.  
  31. What's new?
  32.  
  33. Enhanced Levine book listing (iecc!johnl@ursa-major.spdcc.com).
  34.  
  35. Pixar's address, and Pixar video ordering info (jfr@tellabs.com).
  36.  
  37.         grieggs@jpl-devvax.jpl.nasa.gov
  38.  
  39.  
  40.  
  41. Contents:
  42.  
  43.     1) General references for graphics questions.
  44.     2) Drawing three-dimensional objects on a two-dimensional screen.
  45.     3) Quantizing 24 bit images down to 8 bits.
  46.     4) Converting color into grayscale.
  47.     5) Quantizing grayscale to black&white.
  48.     6) Rotating a raster image by an arbitrary angle.
  49.     7) Free image manipulation software.
  50.     8) Format documents for TIFF, IFF, BIFF, NFF, OFF, FITS, etc.
  51.     9) Converting between vector formats.
  52.     10) How to get Pixar films.
  53.     11) How do I draw a circle as a Bezier (or B-spline) curve?
  54.     12) How to order standards documents.
  55.     13) How to FTP by email.
  56.     14) How to tell whether a point is within a planar polygon.
  57.     15) How to tessellate a sphere.
  58.     16) Specific references on ray-tracing and global illumination.
  59.     17) SIGGRAPH information online
  60.     18) SIGGRAPH Panels Proceedings available
  61.     19) Graphics mailing lists
  62.     20) Specific references on file formats
  63.     21) What about GIF?
  64.     22) What is morphing?
  65.     23) How to ray-trace height fields
  66.     24) How to find the area of a 3D polygon
  67.     25) How to join ACM/SIGGRAPH
  68.     26) Where can I find MRI and CR scan volume data?
  69.     27) Specific references on spatial data structures
  70.  
  71.  
  72. 1) General references for graphics questions:
  73.  
  74.     Computer Graphics: Principles and Practice (2nd Ed.), J.D. Foley,
  75.     A. van Dam, S.K. Feiner, J.F. Hughes, Addison-Wesley 1990, ISBN
  76.     0-201-12110-7
  77.     Procedural Elements for Computer Graphics, David F. Rogers, McGraw
  78.     Hill 1985, ISBN 0-07-053534-5
  79.     Mathematical Elements for Computer Graphics 2nd Ed., David F. Rogers
  80.     and J. Alan Adams, McGraw Hill 1990, ISBN 0-07-053530-2
  81.     Three Dimensional Computer Graphics, Alan Watt, Addison-Wesley 1990, ISBN
  82.     0-201-15442-0
  83.     An Introduction to Ray Tracing, Andrew Glassner (ed.), Academic Press
  84.     1989, ISBN 0-12-286160-4
  85.     Graphics Gems, Andrew Glassner (ed.), Academic Press 1990, ISBN
  86.     0-12-286165-5
  87.     Graphics Gems II, James Arvo (ed.), Academic Press 1991, ISBN
  88.     0-12-64480-0
  89.     Graphics Gems III, David Kirk (ed.), Academic Press 1992, ISBN
  90.     0-12-409670-0 (with IBM disk) or 0-12-409671-9 (with Mac disk)
  91.     Digital Image Warping, George Wolberg, IEEE Computer Society Press
  92.     Monograph 1990, ISBN 0-8186-8944-7
  93.     Digital Image Processing (2nd Ed.), Rafael C. Gonzalez, Paul Wintz,
  94.     Addison-Wesley 1987, ISBN 0-201-11026-1
  95.     A Programmer's Geometry, Adrian Bowyer, John Woodwark, Butterworths 1983,
  96.     ISBN 0-408-01242-0 Pbk
  97.  
  98. An automatic mail handler at Brown University allows users of "Computer
  99. Graphics: Principles and Practice," by Foley, van Dam, Feiner, and
  100. Hughes, to obtain text errata and information on distribution of the
  101. software packages described in the book.  Also, users can send the
  102. authors feedback, to report text errors and software bugs, make
  103. suggestions, and submit exercises.  To receive information describing
  104. how you can use the mail handler, simply mail graphtext@cs.brown.edu
  105. and put the word "Help" in the Subject line.  Use the Subject line
  106. "Software-Distribution" to receive information specifically concerning
  107. the software packages SRGP and SPHIGS.
  108.  
  109. Errata for "An Introduction to Ray Tracing" is available on
  110. wuarchive.wustl.edu in graphics/graphics/books/IntroToRT.errata.
  111.  
  112. Errata for "Digital Image Warping" is in the same directory as
  113. "Digital-Image-Warping.errata".
  114.  
  115. All C code from the "Graphics Gems" series is available via anonymous ftp
  116. from princeton.edu.  Look in the directory pub/Graphics/GraphicsGems for
  117. the various volumes (Gems, GemsII, GemsIII), and get the README file first.
  118.  
  119. Errata to _Graphics Gems_ and _Graphics Gems II is available on
  120. wuarchive.wustl.edu in graphics/graphics/books.
  121.  
  122. A list of computer graphics, computational geometry and image processing
  123. journals is available from Juhana Kouhia, jk87377@cs.tut.fi.
  124.  
  125.  
  126. 2) Drawing three-dimensional objects on a two-dimensional screen.
  127.  
  128. The simple answer is, you divide by the depth.  For a more verbose
  129. explanation, see any of the above references, starting with:
  130.  
  131. The Foley & Van Dam & Feiner & Hughes "Computer Graphics" book is certainly
  132. a good start.  Chapter 6 is "Viewing in 3D", then read chapter 15,
  133. "Visible-Surface Determination".  For more information go to chapter 16 for
  134. shading, chapter 19 for clipping, and branch out from there.
  135.  
  136.  
  137. 3) Quantizing 24 bit images down to 8 bits.
  138.  
  139. Find a copy of "Color Image Quantization for Frame Buffer Display" by
  140. Paul Heckbert, SIGGRAPH '82 Proceedings, page 297.  There are other
  141. algorithms, but this one works well and is fairly simple.  Implementations
  142. are included in most raster toolkits (see item 7 below).
  143.  
  144. A variant method is described in "Graphics Gems", p. 287-293.  Note that
  145. the code from the "Graphics Gems" series is all available from an FTP site,
  146. as described above.
  147.  
  148. Check out John Bradley's "Diversity Algorithm", which is incorporated into
  149. the xv package and described in the back of the manual.
  150.  
  151. The ImageMagick package (see section 7 for where it is) contains another
  152. quantizing algorithm which is presented as "doing a better job than the
  153. other algorithms, but slower".
  154.  
  155. There's also an implementation of:
  156.  
  157. Wan, Wong, and Prusinkiewicz, _An Algorithm for Multidimensional Data
  158. Clustering_, Transactions on Mathematical Software, Vol. 14 #2 (June, 1988),
  159. pp. 153-162.
  160.  
  161. avialable as princeton.edu:pub/Graphics/colorquant.shar.  This code,
  162. in modified form, appears in the Utah Raster Toolkit as well.
  163.  
  164.  
  165. 4) Converting color into grayscale.
  166.  
  167. The NTSC formula is:
  168.  
  169.     luminosity = .299 red + .587 green + .114 blue
  170.  
  171.  
  172. 5) Quantizing grayscale to black&white.
  173.  
  174. The only reference you need for this stuff is:
  175.  
  176.     Digital Halftoning, Robert Ulichney, MIT Press 1987, ISBN 0-262-21009-6
  177.  
  178. But before you go off and start coding, check out the image manipulation
  179. software mentioned in item 7 below.  All of the packages mentioned can do
  180. some form of gray to b&w conversion.
  181.  
  182.  
  183. 6) Rotating a raster image by an arbitrary angle.
  184.  
  185. The obvious but wrong method is to loop over the pixels in the source
  186. image, transform each coordinate, and copy the pixel to the destination.
  187. This is wrong because it leaves holes in the destination.  Instead,
  188. loop over the pixels in the destination image, apply the *reverse*
  189. transformation to the coordinates, and copy that pixel from the source.
  190. This method is quite general, and can be used for any one-to-one
  191. 2-D mapping, not just rotation.  You can add anti-aliasing by doing
  192. sub-pixel sampling.
  193.  
  194. However, there is a much faster method, with antialising included,
  195. which involves doing three shear operations.  The method was originally
  196. created for the IM Raster Toolkit (see below); an implementation is
  197. also present in PBMPLUS.  Reference: "A Fast Algorithm for Raster
  198. Rotation", by Alan Paeth (awpaeth@watcgl.waterloo.edu) Graphics
  199. Interface '86 (Vancouver).  An article on the IM toolkit appears in
  200. the same journal.  An updated version of the rotation paper appears
  201. in "Graphics Gems" (see section [1]) under the original title.
  202.  
  203.  
  204. 7) Free image manipulation software.
  205.  
  206. There are a number of toolkits for converting from one image format to
  207. another, doing simple image manipulations such as size scaling, plus
  208. the above-mentioned 24 -> 8, color -> gray, gray -> b&w conversions.
  209. Here are pointers to some of them:
  210.  
  211.     xv by John Bradley.  X-based image display, manipulation, and format
  212.     conversion package.  XV displays many image formats and permits editing
  213.     of GIF files, among others. The program was updated 5/92; see the file
  214.     contrib/xv-2.21.tar.Z on export.lcs.mit.edu.
  215.  
  216.     PBMPLUS, by Jef Poskanzer.  Comprehensive format conversion and image
  217.     manipulation package.  The latest version is always available via
  218.     anonymous FTP as ftp.ee.lbl.gov:pbmplus*.tar.Z,
  219.     wuarchive.wustl.edu:graphics/graphics/packages/pbmplus/pbmplus*.tar.Z,
  220.     and export.lcs.mit.edu:contrib/pbmplus*.tar.Z.
  221.  
  222.     IM Raster Toolkit, by Alan Paeth (awpaeth@watcgl.uwaterloo.ca).
  223.     Provides a portable and efficient format and related toolkit.  The
  224.     format is versatile in supporting pixels of arbitrary channels,
  225.     components, and bit precisions while allowing compression and machine
  226.     byte-order independence.  The kit contains more than 50 tools with
  227.     extensive support of image manipulation, digital halftoning and format
  228.     conversion.  Previously distributed on tape c/o the University of
  229.     Waterloo, an FTP version will appear someday.
  230.  
  231.     Utah RLE Toolkit.  Conversion and manipulation package, similar to
  232.     PBMPLUS.  Available via FTP as cs.utah.edu:pub/urt-*,
  233.     princeton.edu:pub/Graphics/urt-*, and freebie.engin.umich.edu:pub/urt-*.
  234.  
  235.     Fuzzy Pixmap Manipulation, by Michael Mauldin <mlm@nl.cs.cmu.edu>.
  236.     Conversion and manipulation package, similar to PBMPLUS.  Version 1.0
  237.     available via FTP as nl.cs.cmu.edu:/usr/mlm/ftp/fbm.tar.Z,
  238.     ftp.uu.net:pub/fbm.tar.Z, and ucsd.edu:graphics/fbm.tar.Z.
  239.  
  240.     Img Software Set, by Paul Raveling <raveling@venera.isi.edu>.  Reads and
  241.     writes its own image format, displays on an X11 screen, and does some
  242.     image manipulations.  Version 1.3 is available via FTP as
  243.     export.lcs.mit.edu:contrib/img_1.3.tar.Z, and
  244.     venera.isi.edu:pub/img_1.3.tar.Z along with a large collection of color
  245.     images.
  246.  
  247.     Xim, X Image Manipulator, by Philip R. Thompson.  It does essential
  248.     interactive image manipulations and uses x11r4 and the OSF/Motif toolkit
  249.     for the interface.  It supports images in 1, 8, 24 and 32 bit formats.
  250.     Reads/writes and converts to/from GIF, xwd, xbm, tiff, rle, xim, and
  251.     other formats.  Writes level 2 postscript.  Other utilities and image
  252.     application library are included.  Not a paint package.  Available via
  253.     ftp from gis.mit.edu.
  254.  
  255.     xloadimage, by Jim Frost <madd@std.com>.  Reads in images in various
  256.     formats and displays them on an X11 screen.  Available via FTP as
  257.     export.lcs.mit.edu:contrib/xloadimage*, and in your nearest comp.sources.x
  258.     archive.
  259.  
  260.     xli, by Grame Gill, is an updated xloadimage with numerous improvements
  261.     in both speed and in the number of formats supported.  Available in the
  262.     same places as xloadimage (contrib tape, comp.sources.x archives).
  263.  
  264.     TIFF Software, by Sam Leffler <sam@okeeffe.berkeley.edu>.  Nice
  265.     portable library for reading and writing TIFF files, plus a few tools
  266.     for manipulating them and reading other formats.  Available via FTP as
  267.     ucbvax.berkeley.edu:pub/tiff/*.tar.Z or ftp.uu.net:graphics/tiff.tar.Z
  268.  
  269.     xtiff, an X11 tool for viewing a TIFF file.  It was written to handle
  270.     as many different kinds of TIFF files as possible while remaining
  271.     simple, portable and efficient.  xtiff illustrates some common problems
  272.     with building pixmaps and using different visual classes.  It is
  273.     distributed as part of Sam Leffler's libtiff package and it is also
  274.     available on export.lcs.mit.edu, ftp.uu.net and comp.sources.x.
  275.     xtiff 2.0 was announced in 4/91; it includes Xlib and Xt versions.
  276.  
  277.     ALV, a Sun-specific image toolkit.  Version 2.0.6 posted to
  278.     comp.sources.sun on 11dec89.  Also available via email to
  279.     alv-users-request@cs.bris.ac.uk.
  280.  
  281.     popi, an image manipulation language.  Version 2.1 posted to
  282.     comp.sources.misc on 12dec89.
  283.  
  284.     ImageMagick, an X11 package for display and interactive manipulation
  285.     of images.  Includes tools for image conversion, annotation, compositing,
  286.     animation, and creating montages.  ImageMagick can read and write many of
  287.     the more popular image formats.  Available via FTP as
  288.     export.lcs.mit.edu:contrib/ImageMagick.tar.Z.
  289.  
  290.     Khoros, a huge (~100 meg) graphical development environment based on
  291.     X11R4.  Khoros components include a visual programming language, code
  292.     generators for extending the visual language and adding new application
  293.     packages to the system, an interactive user interface editor, an
  294.     interactive image display package, an extensive library of image and
  295.     signal processing routines, and 2D/3D plotting packages.  Available via
  296.     FTP as pprg.eece.unm.edu:pub/khoros/*.
  297.  
  298.     LaboImage, a SunView-based image processing and analysis package.  It
  299.     includes more than 200 image manipulation, processing and measurement
  300.     routines, on-line help, plus tools such as an image editor, a color
  301.     table editor and several biomedical utilities.  Available via anonymous
  302.     FTP as ads.com:pub/VISION-LIST-ARCHIVE/SHAREWARE/LaboImage_3.1.tar.Z
  303.  
  304.     The San Diego Supercomputer Center Image Tools, software tools for
  305.     reading, writing, and manipulating raster images.  Binaries for some
  306.     machines available via anonymous FTP in sdsc.edu:sdscpub.
  307.  
  308.     The Independent JPEG Group has written a package for reading and
  309.     writing JPEG files.  FTP to ftp.uu.net:graphics/jpeg/jpegsrc.v?.tar.Z
  310.  
  311. Don't forget to set binary mode when you FTP tar files.  For you MILNET
  312. folks who still don't have name servers, the IP addresses are:
  313.  
  314.     ads.com            128.229.30.16
  315.     cs.utah.edu            128.110.4.21
  316.     coral.cs.jcu.edu.au        137.219.17.4
  317.     export.lcs.mit.edu        18.24.0.12
  318.     freebie.engin.umich.edu    141.212.103.21
  319.     ftp.ee.lbl.gov        128.3.112.20
  320.     ftp.uu.net            137.39.1.9 or 192.48.96.9
  321.     gis.mit.edu            18.80.1.118
  322.     gondwana.ecr.mu.oz.au    128.250.70.62
  323.     karazm.math.uh.edu        129.7.7.6
  324.     marsh.cs.curtin.edu.au    134.7.1.1
  325.     nic.funet.fir        128.214.6.100
  326.     ftp.cosy.sbg.ac.at        141.201.2.15
  327.     ftp.ncsa.uiuc.edu        141.142.20.50
  328.     nl.cs.cmu.edu        128.2.222.56
  329.     pprg.eece.unm.edu        129.24.24.10
  330.     princeton.edu        128.112.128.1
  331.     sdsc.edu            132.249.20.22
  332.     ucbvax.berkeley.edu        128.32.133.1
  333.     venera.isi.edu        128.9.0.32
  334.     weedeater.math.yale.edu    128.36.23.17
  335.     wuarchive.wustl.edu        128.252.135.4
  336.     zamenhof.cs.rice.edu    128.42.1.75
  337.  
  338. Please do *not* post or mail messages saying "I can't FTP, could someone
  339. mail this to me?"  There are a number of automated mail servers that will
  340. send you things like this in response to a message.  See item 13 below for
  341. details on some.
  342.  
  343. Also, the newsgroup alt.graphics.pixutils is specifically for discussion
  344. of software like this.  You may find useful information there.
  345.  
  346.  
  347. 8) Format documents for TIFF, IFF, BIFF, NFF, OFF, FITS, etc.
  348.  
  349. You almost certainly don't need these.  Read the above item 7 on free
  350. image manipulation software.  Get one or more of these packages and
  351. look through them.  Chances are excellent that the image converter you
  352. were going to write is already there.  But if you still want one of the
  353. format documents, many such files are available by anonymous ftp from
  354. zamenhof.cs.rice.edu in directory pub/graphics.formats.  It is also
  355. mirrored at ftp.cosy.sbg.ac.at in dir /pub/mirror/file-formats/graphic.
  356.  
  357. These files were collected off the net and are believed to be correct.
  358. This archive includes pixel formats, and two- and three-dimensional object
  359. formats.  The future of this archive is uncertain at the moment, as Mark
  360. Hall <foo@cs.rice.edu> will apparently no longer be maintaining it.
  361.  
  362. A second graphics file format archive is now being actively maintained
  363. by Quincey Koziol (koziol@ncsa.uiuc.edu).  The latest version exists at
  364. ftp.ncsa.uiuc.edu in /misc/file.formats/graphics.formats.  Apparently,
  365. neither of these is complete, you might want to check both.
  366.  
  367. FITS stands for Flexible Image Transport System, it's an image file
  368. format most often used in astronomy.  Refer to the sci.space FAQ for
  369. more information if needed.
  370.  
  371.  
  372. 9) Converting between vector formats.
  373.  
  374. A lot of people ask about converting from HPGL to PostScript, or MacDraw
  375. to CGM, or whatever.  It is important to understand that this is a very
  376. different problem from the image format conversions in item 7.  Converting
  377. one image format to another is a fairly easy problem, since once you
  378. get past all the file header junk, a pixel is a pixel -- the basic objects
  379. are the same for all image formats.  This is not so for vector formats.
  380. The basic objects -- circles, ellipses, drop-shadowed pattern-filled
  381. round-cornered rectangles, etc. -- vary from one format to another.
  382. Except in extremely restricted cases, it is simply not possible to do
  383. a one-to-one conversion between vector formats.
  384.  
  385. On the other hand, it is quite possible to do a close approximation,
  386. rendering an image from one format using the primitives from another.
  387. As far as I know, no one has put together a general toolkit of such
  388. converters, but two different HPGL to PostScript converters have been
  389. posted to comp.sources.misc.  Check the index on your nearest archive
  390. site.
  391.  
  392. A related frequent question is how to convert from some vector format
  393. to a bitmapped image - from PostScript to Sun raster format, or HPGL to
  394. X11 bitmap.  For example, some of the commercial PostScript clones for
  395. PC's allow you to render to a disk file as well as a printer.  Also,
  396. the PostScript interpreters in the NeXT box and in Sun's X11/NeWs can
  397. be used to render to a file if you're clever.  But in general, the
  398. answer is no.  However, if someone were to put together a vector to
  399. vector conversion toolkit, adding a vector to raster converter would be
  400. trivial.
  401.  
  402. GNU ghostscript (from the FSF - current version 2.5.2) includes
  403. drivers for both ppm and gif format files, thus it can be used as
  404. a PostScript to ppm  or a PostScript to GIF filter.  (It implements
  405. essentially all of PostScript level 1 and alot of Display PostScript
  406. and level 2).
  407.  
  408.  
  409. 10) How to get Pixar films.
  410.  
  411. The various John Lasseter / Pixar computer animated shorts are available
  412. on video tape.  You can order them from Direct Cinema Limited:
  413.  
  414.     Film                           Individual Price      Institutional Price
  415.     Luxo, Jr.                $14.95            $50.00
  416.     Red's Dream                $19.95            $75.00
  417.     Tin Toy                $24.95            $75.00
  418.     Knickknack                $24.95            $75.00
  419.     Luxo, Jr./Red's Dream/Tin Toy    $39.95            $100.00
  420.  
  421. All tapes are on 1/2" VHS NTSC.  Add $10/tape for PAL format.  Also
  422. available:
  423.  
  424.     Tin Toy T-shirt            $15.00
  425.     Knickknack 3D T-shirt        $15.00 (includes glasses)
  426.  
  427. For individual orders, add $5 S&H for the first tape or shirt, $2 for
  428. each additional tape or shirt.  For institutional orders, add $5 S&H
  429. for the first tape, $3 for each additional tape.  Foreign shipping, add
  430. $3/tape or shirt.  Call 800-525-0000 (213-396-4774 international,
  431. 213-396-3233 FAX) to charge to your credit card.  Call first to verify
  432. prices and availability.  Or, just write to:
  433.  
  434.     Direct Cinema Limited
  435.     1749 14th Street
  436.     Santa Monica, CA 90404-4342
  437.  
  438. Allan Braunsdorf has this to say:
  439.  
  440. At SIGGRAPH they were selling a tape with all four shorts
  441. for $25.  That was a sale price.  You can get it for slightly
  442. more than that normally.  ($35 maybe.)  I believe it's
  443. available from RenderMan Retail (at Pixar's address).
  444.  
  445.     Pixar
  446.     1001 West Cutting Blvd.
  447.     Richmond, CA. 94804
  448.     (510) 236-4000 
  449.     (510) 236-0388 (FAX)
  450.  
  451. You can obtain a video directly from Pixar which contains "Luxo, Jr.", "Red's
  452. Dream", "Tin Toy" and "Knicknack" for $25.00, plus $2.50 for shipping. They
  453. will take your order over the phone or via FAX with a major credit card. I 
  454. ordered mine just last week and received it several days later. Don't expect 
  455. to be able to rent a copy from your local video store. According to the license
  456. agreement printed on the back cover of the case, it cannot be rented.
  457.  
  458.  
  459. 11) How do I draw a circle as a Bezier (or B-spline) curve?
  460.  
  461. The short answer is, "You can't."  Unless you use a rational spline you
  462. can only approximate a circle.  The approximation may look acceptable,
  463. but it is sensitive to scale.  Magnify the scale and the error of
  464. approximation magnifies.  Deviations from circularity that were not
  465. visible in the small can become glaring in the large.  If you want to
  466. do the job right, consult the article:
  467.  
  468.   "A Menagerie of Rational B-Spline Circles"
  469.   by Leslie Piegl and Wayne Tiller
  470.   in IEEE Computer Graphics and Applications, volume 9, number 9,
  471.   September, 1989, pages 48-56.
  472.  
  473. For rough, non-rational approximations, consult the book:
  474.  
  475.   Computational Geometry for Design and Manufacture
  476.   by I. D. Faux and M. J. Pratt,
  477.   Ellis Horwood Publishers, Halsted Press, John Wiley 1980.
  478.  
  479. For the best known non-rational approximations, consult the article:
  480.  
  481.   "Good Approximation of Circles by Curvature-continuous Bezier Curves"
  482.   by Tor Dokken, Morten Daehlen, Tom Lyche, and Knut Morken
  483.   in Computer Aided Geometric Design, volume 7, numbers 1-4 (combined),
  484.   June, 1990, pages 33-41 [Elsevier Science Publishers (North-Holland)]
  485.  
  486.  
  487. 12) How to order standards documents.
  488.  
  489. The American National Standards Institute sells ANSI standards, and also
  490. ISO (international) standards.  Their sales office is at 1-212-642-4900,
  491. mailing address is 1430 Broadway, NY NY 10018.  It helps if you have the
  492. complete name and number.
  493.  
  494. Some useful numbers to know:
  495.  
  496. CGM (Computer Graphics Metafile) is ISO 8632-4 (1987).  GKS (Graphical
  497. Kernel System) is ANSI X3.124-1985.  PHIGS (Programmer's Hierarchical
  498. Interactive Graphics System) is ANSI X3.144-1988.  IGES is ASME/ANSI
  499. Y14.26M-1987.  Language bindings are often separate but related numbers;
  500. for example, the GKS FORTRAN binding is X3.124.1-1985.
  501.  
  502. Standards-in-progress are made available at key milestones to solicit
  503. comments from the graphical public (this includes you!).  ANSI can let
  504. you know where to order them; most are available from Global Engineering
  505. at 1-800-854-7179.
  506.  
  507.  
  508. 13) How to FTP by email.
  509.  
  510. There are a number of sites that archive the Usenet sources newsgroups
  511. and make them available via an email query system.  You send a message
  512. to an automated server saying something like "send comp.sources.unix/fbm",
  513. and a few hours or days later you get the file in the mail.
  514.  
  515. In addition, there is at least one FTP-by-mail server.  Send mail to
  516. ftpmail@decwrl.dec.com saying "help" and it will tell you how to use
  517. it.  Note that this service has at times been turned off due to abuse.
  518.  
  519.  
  520. 14) How to tell whether a point is within a planar polygon.
  521.  
  522. Consider a ray originating at the point of interest and continuing to
  523. infinity.  If it crosses an odd number of polygon edges along the way,
  524. the point is within the polygon.  If the ray crosses an even number of
  525. edges, the point is either outside the polygon, or within an interior
  526. hole formed from intersecting polygon edges.  This idea is known in
  527. the trade as the Jordan curve theorem; see Eric Haines' article in
  528. Glassner's ray tracing book (above) for more information, including
  529. treatment of special cases.
  530.  
  531. Another method is to sum the absolute angles from the point to all
  532. the vertices on the polygon.  If the sum is 2 pi, the point is inside,
  533. if the sum is 0 the point is outside.  However, this method is about an
  534. order of magnitude slower than the previous method because evaluating the
  535. trigonometric functions is usually quite costly.
  536.  
  537. Code for both methods (plus barycentric triangle testing) can be found in
  538. the Ray Tracing News, Vol. 5, No. 3, available from princeton.edu:
  539. pub/Graphics/RTNews/RTNv5n3.Z.
  540.  
  541.  
  542. 15) How to tessellate a sphere.
  543.  
  544. One simple way is to do recursive subdivision into triangles.  The
  545. base of the recursion is an octahedron, and then each level divides
  546. each triangle into four smaller ones.  Jon Leech <leech@cs.unc.edu>
  547. has posted a nice routine called sphere.c that generates the coordinates.
  548. It's available for FTP on ftp.ee.lbl.gov and princeton.edu.
  549.  
  550. 16) Specific references on ray-tracing and global illumination.
  551.  
  552. Rick Speer maintains a cross-indexed ray-tracing bibliography:
  553.  
  554. Highlights of this edition-
  555.  
  556.     i) more than 500 citations spanning the period from 1968 through
  557.        November '91;
  558.     ii) papers from all Siggraph, Graphics Interface, Eurographics, CG
  559.         International and Ausgraph proceedings through December, '91;
  560.     iii) all citations keyworded for easy lookup;
  561.     iv) cross-indices by keyword and author;
  562.     v)  glossary of the 119 keywords used.
  563.  
  564. The bib is in the form of a PostScript file.  The printout is 41 pages long.
  565. Below is a list of ftp sites and the dirs that contain the file. It's named
  566. "speer.raytrace.bib.ps.Z" and is compressed at most sites-
  567.  
  568.              Site                             Dir
  569.     wuarchive.wustl.edu    graphics/graphics/bib/RT.BIB.Speer/
  570.     karazm.math.uh.edu    pub/Graphics/
  571.     gondwana.ecr.mu.oz.au    pub/papers/
  572.     nic.funet.fi        pub/sci/papers/graphics
  573.     coral.cs.jcu.edu.au     graphics/papers/
  574.  
  575. Eric Haines (erich@eye.com) maintains ray tracing and radiosity/global
  576. illumination bibliographies.  These are in "refer" format, and so can be
  577. searched electronically (a simple awk script to search for keywords is
  578. included with each).  The bibliographies are available at most of the
  579. sites listed above, and the most current versions are maintained at
  580. princeton.edu: pub/Graphics/Papers as "RayBib.*" and "RadBib.*".
  581.  
  582. Tom Wilson (wilson@cs.ucf.edu) has collected over 300 abstracts from ray
  583. tracing related research papers and books.  The information is essentially
  584. in plaintext, and Latex and troff formatting programs are included.  This
  585. collection is available at most of the sites above as "rtabs.*".
  586.  
  587. 17) SIGGRAPH information online
  588.  
  589. [from Steve Cunningham and Ralph Orlick]
  590.  
  591. ACM-SIGGRAPH announces its online information site at  siggraph.org
  592. (128.248.245.250).  This site now provides SIGGRAPH information via both
  593. anonymous ftp and an electronic mail archive server.
  594.  
  595. The anonymous ftp service is very standard, and the ftp directory includes
  596. both conference and publications subdirectories.
  597.  
  598. To retrieve information by electronic mail, send mail to
  599.      archive-server@siggraph.org
  600. and in the subject or the body of the message include the message  send
  601. followed by the topic and subtopic you wish.  A good place to start is with
  602. the command
  603.      send index
  604. which will give you an up-to-date list of available information.
  605.  
  606.  
  607. 18) SIGGRAPH Panels Proceedings available
  608.  
  609. [from Steve Cunningham and Bob Judd]
  610.  
  611. ACM SIGGRAPH announces the availability of the SIGGRAPH '91 Panels Proceedings
  612. at the  siggraph.org  site (128.248.245.250).  The proceedings are available
  613. in three formats:
  614.      text   (ASCII)
  615.      rtf    (rich text format, suitable for many word processors)
  616.      word   (MS Word for the Macintosh)
  617. They may be retrieved from siggraph.org in two ways:
  618.  
  619. (1) by anonymous ftp
  620.     change to one of the directories
  621.        publications/s91/panels_proceedings/[text|rtf|word]
  622.     The text and rtf files may be downloaded in ASCII mode, while the word
  623.     files are stored in MacBinary format and must be downloaded in binary 
  624.     mode.
  625.  
  626.     Each directory contains a Table of Contents file (TOC) that describes the
  627.     contents of each panel file.
  628.  
  629. (2) by electronic mail
  630.     send mail to
  631.        archive-server@siggraph.org
  632.     You can retrieve either the  text  or  rtf  files.  We suggest that you
  633.     first retrieve the index files by putting one of the messages
  634.        send panel91-txt index
  635.        send panel91-rtf index
  636.     in the subject or body of the message.  You will get the necessary
  637.     information to retrieve the actual transcript files.
  638.  
  639.  
  640. 19) Graphics mailing lists
  641.  
  642. There are a variety of graphics-related mailing list out there, each
  643. covering either a single product or a single topic.  I have been an
  644. active participant in one of these for some time now, and find the
  645. focus and expertise which can be brought to bear on an isolated topic
  646. to be nothing short of amazing.
  647.  
  648. Please send me the appropriate information if you have any others you
  649. would like to see added.
  650.  
  651. Name:        Imagine mailing list
  652. Description:    Discussion forum for users of the Imagine 3D Rendering and
  653.         Animation package by Impulse, Inc.
  654. Platforms:    Amiga
  655. Subscription:    imagine-request@email.sp.paramax.com
  656. Posting:    imagine@email.sp.paramax.com
  657.  
  658. Name:        DCTV mailing list
  659. Description:    Discussion forum for users of the Digital Creations DCTV
  660.         box, software, and file formats
  661. Platforms:    Amiga
  662. Subscription:    DCTV-request@nova.cc.purdue.edu
  663. Posting:    DCTV@nova.cc.purdue.edu
  664.  
  665. Name:        Rayshade Users mailing list
  666. Description:    Discussion forum for users of the Rayshade raytracer
  667. Platforms:    Most UNIX boxes, Amiga, Mac, IBM
  668. Subscription:    rayshade-request@cs.princeton.edu
  669. Posting:    rayshade-users@cs.princeton.edu
  670.  
  671. Name:        Lightwave 3D software for Toaster mailing list
  672. Description:    Discussion forum for users of Lightwave, the Video
  673.         Toaster modelling and rendering package
  674. Platforms:    Amiga
  675. Subscription:    lightwave-request@bobsbox.rent.com
  676.         with "subscribe lightwave-l" in your message
  677. Posting:    lightwave@bobsbox.rent.com
  678.  
  679. Name:        POV mailing list
  680. Description:    Discussion forum for DKBTrace and POV renderers
  681. Platforms:    Unix
  682. Subscription:    listserv@trearn.bitnet
  683. Posting:    dkb-l@trearn.bitnet
  684.  
  685. Name:        Mailing List For Massive Parallel Rendering
  686. Description:    same?
  687. Platforms:    Unix
  688. Subscription:    mp-render-request@icase.edu
  689. Posting:    mp-render@icase.edu
  690.  
  691. 20) Specific references on file formats
  692.  
  693.     Graphics File Formats, David Kay and John Levine, Windcrest/McGraw-Hill
  694.       1992, ISBN 0-8306-3059-7 paper, ISBN 0-8306-3060-0 $36.95 hardcover,
  695.       ISBN 0-8306-3059-7 $24.95 paper.  Comments - 26 formats, no software
  696.       (this is good, IMHO - I prefer books which are non-platform-dependent).
  697.       Questions about this book may be sent to gbook@iecc.cambridge.ma.us.
  698.  
  699.  
  700. 21) What about GIF?
  701.  
  702. GIF stands for Graphics Interchange Format.  It is portable and usable upon
  703. a wide variety of platforms.  It is quite limited in some ways (yes, the
  704. keeper of the FAQ has some opinions after all), and in fact, I don't like
  705. it much.  However, it looks to me like the most-Frequently Asked Question
  706. which was not previously covered in this list.  The following is a list
  707. of newsgroups and the like where one could go to find out about GIF.
  708.  
  709. Subject: alt.binaries.pictures FAQ - General info
  710. Subject: alt.binaries.pictures FAQ - OS specific info
  711. Newsgroups: alt.binaries.pictures.d,alt.binaries.pictures.misc,
  712.     alt.binaries.pictures.utilities,alt.binaries.pictures.fractals,
  713.     alt.binaries.pictures.fine-art.d,news.answers
  714.  
  715. Available in the indicated USENET newsgroup(s), or via anonymous ftp from
  716. pit-manager.mit.edu (18.172.1.27) in the files:
  717.  
  718. /pub/usenet/news.answers/pictures-faq/part1
  719. /pub/usenet/news.answers/pictures-faq/part2
  720.  
  721. Also available from mail-server@pit-manager.mit.edu by sending a mail
  722. message containing any or all of:
  723.  
  724. send usenet/news.answers/pictures-faq/part1
  725. send usenet/news.answers/pictures-faq/part2
  726.  
  727. Send a message containing "help" to get general information about the
  728. mail server.
  729.  
  730. Also, you could check out the resources described in sections 7, 8, and
  731. 20 above for more information.
  732.  
  733.  
  734. 22) What is morphing?
  735.  
  736. Warping is the deformation of an image by mapping each pixel to a new
  737. location. Morphing is blending from one image or object to another one.
  738. Valerie Hall has written an excellent introduction to warping and
  739. morphing. This is available for anonymous ftp from marsh.cs.curtin.edu.au
  740. in the directory pub/graphics/bibliography/Morph. There are three files:
  741.  
  742.         morph_intro.ps.Z     (PostScript version, many pictures - 1.5M)
  743.         morph_intro.txt.Z    (text version)
  744.         m_responses.Z        (Responses to morphing questions)
  745.  
  746. The files are compressed, so you must use binary transfer and
  747. uncompress them afterwards.
  748.  
  749.  
  750. 23) How to ray-trace height fields
  751.  
  752. Height fields are a special case in ray-tracing.  They have a number of uses,
  753. such as terrain rendering, and some optimization is possible.  Thus, they
  754. get their own FAQ section.  Note that further references can no doubt be
  755. located via the ray-tracing bibs in section 16 above.
  756.  
  757. The following paper seems to be the definitive reference:
  758.  
  759. F. Kenton Musgrave
  760. Grid Tracing: Fast Ray Tracing For Height Fields
  761. July, 1988
  762. <musg88.ps.Z>
  763.  
  764. This is available as "Research Report YALEU/DCS/RR-639" from Yale University,
  765. it's also in the SIGGRAPH '91 Fractal Modeling in 3D Computer Graphics and
  766. Imaging course notes, and (best of all) it's available on the net:
  767.  
  768.     nic.funet.fi        pub/sci/papers/musg88.ps.Z
  769.     weedeater.math.yale.edu    pub/Papers/musg88.ms.Z
  770.     princeton.edu        pub/Graphics/Papers/musg88.ms.Z
  771.     coral.cs.jcu.edu.au        graphics/papers/musg88.ps.Z
  772.     gondwana.ecr.mu.OZ.AU    pub/papers/musg88.ms.Z and musg88.ps.Z
  773.  
  774. An implementation of this paper may be found in Rayshade.
  775.  
  776. Another paper exists:
  777.  
  778. %A David W. Paglieroni
  779. %A Sidney M. Petersen
  780. %T Parametric Height Field Ray Tracing
  781. %J Proceedings of Graphics Interface '92
  782. %I Canadian Information Processing Society
  783. %C Toronto, Ontario
  784. %D May 1992
  785. %P 192-200
  786.  
  787. And still one more:
  788.  
  789. Musgrave, Kolb, and Mace
  790. "The Synthesis and Rendering of Eroded Fractal Terrains",
  791. Computer Graphics Vol 23, No. 3 (SIGGRAPH '89 procedings) p. 41-50
  792.  
  793.  
  794.  
  795. 24) How to find the area of a 3D polygon
  796.  
  797.     The area of a triangle is given by (in C notation),
  798.  
  799.      area = 0.5 * ( ( x[0] * y[1] ) + ( x[1] * y[2] ) + ( x[2] * y[0] ) -
  800.                 ( x[1] * y[0] ) - ( x[2] * y[1] ) - ( x[0] * y[2] ) );
  801.  
  802. and the area of a planar polygon is given by
  803.  
  804.      area = 0.0;
  805.  
  806.      for ( i = 0; i < n - 1; i++ )
  807.          area += ( x[i] * y[i + 1] ) - ( x[i + 1] * y[i] );
  808.      area += ( x[n - 1] * y[0] ) - ( x[0] * y[n - 1] );
  809.      area /= 2.0;
  810.  
  811. If the area is a negative number, the polygon or triangle is
  812. clockwise, if positive, it is counterclockwise.
  813.  
  814. >From Ronald Golman's Gem (in Graphics Gems II - see section 1 above), "Area
  815.  of Planar Polygons and Volume of Polyhedra:"
  816.  
  817. The area of a polygon P0, P1, P2, ... Pn, not in the x-y plane, is
  818. given by
  819.  
  820.      Area(Polygon) = 1/2 * | N . Sigma { Pk x Pk+1 } |
  821.  
  822. where N is the unit vector normal to the plane and P is a polygonal
  823. vertex.  The . represents the dot product operator and the x
  824. represents the cross product operator.  Sigma represents the summation
  825. operator.  | | represents the absolute value operator.  Pn+1 is equal
  826. to P0.
  827.  
  828.  
  829. 25) How to join ACM/SIGGRAPH
  830.  
  831. Probably the easiest way to join ACM/SIGGRAPH is to trot over to your
  832. local technical library and find a copy of Communications of the ACM.
  833. Somewhere within the first few pages will be an application blank.
  834. Fill it out and mail it in.  ACM membership for students costs $23.00,
  835. Voting or Associate Membership $77.00 (yearly)
  836.  
  837. SIGGRAPH student membership costs an additional $16.00, $26.00 for
  838. Voting or Associate Members (also yearly).  To get TOG (Transactions
  839. on Graphics) it's another $26.00 for students and $31.00 for Voting or
  840. Associate Members.
  841.  
  842. If you just want to join SIGGRAPH without joining ACM, it'll cost you
  843. $59.00 (no student discount).
  844.  
  845. There are surcharges for overseas airmailing of publications.
  846.  
  847. ACM Member services may be contacted via email at acmhelp@acmvm.bitnet. 
  848. Their phone number is (212) 626-0500.  FAX number (212) 944-1318.
  849. Snailmail address:
  850.  
  851.                 ACM
  852.                 PO Box 12114
  853.                 Church Street Station
  854.                 New York, New York 10257
  855.  
  856. SIGGRAPH `93 will be held in Anaheim, California, at the Anaheim
  857. Convention Center (just up the street from Disneyland) on August 1-6, 1993.
  858.  
  859. 26) Where can I find MRI and CR scan volume data?
  860.  
  861. Volume data sets are available from the University of North Carolina at
  862. omicron.cs.unc.edu (152.2.128.159) in /pub/softlab/CHVRTD.  (Commerical
  863. use is prohibited.)
  864.  
  865. Head data - A 109-slice MRI data set of a human head.
  866.  
  867. Knee data - A 127-slice MRI data set of a human knee.
  868.  
  869. HIPIP data - The result of a quantum mechanical calculation of a SOD data
  870. of a one-electron orbital of HIPIP, an iron protein.
  871.  
  872. SOD data - An electron density map of the active site of SOD (superoxide
  873. dismutase). 
  874.  
  875. CT Cadaver Head data - A 113-slice MRI data set of a CT study of a cadaver
  876. head. 
  877.  
  878. MR Brain data -  A 109-slice MRI data set of a head with skull partially
  879. removed to reveal brain.
  880.  
  881. RNA data - An electron density map for Staphylococcus Aureus Ribonuclease.
  882.  
  883.  
  884. 27) Specific references on spatial data structures
  885.  
  886. H. Samet,
  887. The Design and Analysis of Spatial Data Structures,
  888. Addison-Wesley, Reading, MA, 1990.
  889. ISBN 0-201-50255-0.
  890.  
  891. H. Samet,
  892. Applications of Spatial Data Structures:  Computer Graphics, Image Processing, a
  893. nd GIS,
  894. Addison-Wesley, Reading, MA, 1990.
  895. ISBN 0-201-50300-0.
  896.  
  897. -- 
  898. John T. Grieggs (Telos @ Jet Propulsion Laboratory)
  899. 4800 Oak Grove Drive, Pasadena, Ca. 91109 M/S 525-3660    (818) 306-6506
  900. Uucp: {cit-vax,elroy,chas2}!jpl-devvax!grieggs
  901. Arpa: ...jpl-devvax!grieggs@cit-vax.ARPA
  902.